#
# @lc app=leetcode.cn id=343 lang=python
#
# [343] 整数拆分
#

# @lc code=start
class Solution(object):
    def integerBreak(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 1:
            return 1
        if n == 2:
            return 1
        if n == 3:
            return 2

        result = 1
        while n>4:
            result *= 3
            n -= 3
        result *= n
        return result
        
# @lc code=end

